package com.yyf.springboot2.Test;



import java.util.Stack;

public class TestLinkList {
    /**
     * 单链表的创建
     */

    public Node head;  // 头节点  这是一个node 叫head 的
    public Node current; //当前节点

    //向链表中添加数据
    public void add(int data){
        //1.首先判断该链表是否为空,为空表示不存在,,需要创建,并且把新的节点赋给头节点
        if(head == null){
            head = new Node(data);
            current = head;
        }else{
            //2.如果头节点不为空表示链表已存在,只需要把创建新的节点,放在当前节点的后面
            current.next = new Node(data);
            current =current.next;

        }
    }


    //方法重载：向链表中添加结点
     public void add2(Node node) {
                if (node == null) {
                        return;
                    }

                if (head == null) {
                     head = node;
                      current = head;
                    } else {
                        current.next = node;
                     current = current.next;
                  }
           }


    /**
     * 调用这个方法打印节点
     * @param node 从指定的节点开始遍历
     */
    public void print(Node node){
        if(node == null){
           return;
        }
        current = node;
        while (current != null){
            System.out.println(current.data);
            current = current.next;//执行完方法之后把下一节点设置为当前节点
        }
    }





    /**
     * 获取单个链表中节点的个数,需要检查链表是否为空
     */
    public int getNodeLength(Node head){
        if(head == null){
            return 0;
        }
        int length = 0;
        Node curreng = head;
        while (curreng != null){
            length++;
            curreng = current.next;
        }
        return  length;
    }


    /**
     * 查找单链表中的倒数第k个节点
     * 方法一，遍历整个连表，得到整个链表的长度，然后在遍历一次。取出第k个节点的数据，起始位置为k-1  结束位置为k
     * 方法二,在不允许遍历链表的长度的情况下，的思路
     **/

    public int findLastNode(int index) {  //index代表的是倒数第index的那个结点
        int size = 0 ;
        //第一次遍历，得到链表的长度size
        if (head == null) {
            return -1;
        }

        current = head;
        while (current != null) {
            size++;
            current = current.next;
        }

        //第二次遍历，输出倒数第index个结点的数据
        current = head;  //不停的覆盖索引指向的值
        for (int i = 0; i < size - index; i++) {
            current = current.next;
        }

        return current.data; //返回的就是k节点的值
    }


    /**
     *查出链表中倒数第k个点的数据
     * @param head 链表
     * @param k 指定的k值
     * @return
     */
    public Node findLastNode(Node head, int k) {
        if (k == 0 || head == null) {
            return null;
        }
        Node first = head;
        Node second = head;

        //让second结点往后挪k-1个位置
        for (int i = 1; i <= k - 1; i++) {
            second = second.next;
            if (second == null) { //说明k的值已经大于链表的长度了
                //throw new NullPointerException("链表的长度小于" + k); //我们自己抛出异常，给用户以提示
                return null;
            }
        }
        System.out.println(second.data);
        //让first和second结点整体向后移动，直到second走到最后一个结点
        while (second.next != null) {
            first = first.next;
            second = second.next;
        }
        //当second结点走到最后一个节点的时候，此时first指向的结点就是我们要找的结点
        return first;
    }


    /**
     * 合并2个有序的链表
     * @param head1 链表1
     * @param head2 链表2
     * @return
     */
    //两个参数代表的是两个链表的头结点
    public Node mergeLinkList(Node head1, Node head2) {

        if (head1 == null && head2 == null) {  //如果两个链表都为空
            return null;
        }
        //如果其中一个链表为空,那么就返回另一个不为空的链表
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }

        Node head; //新链表的头结点
        Node current;  //current结点指向新链表

        // 一开始，我们让current结点指向head1和head2中较小的数据，得到head结点
        //依次比较链表1和链表2的头部数据,把比较小的设置为新链表的头节点,如果2个链表的头节点相同把链表1/链表2的头节点设置为新链表的头节点
       //并将游标设置到头节点的后一个元素,另一个链表的游标不变

        if (head1.data < head2.data) {
            head = head1;
            current = head1;
            head1 = head1.next;
        } else {
            head = head2;
            current = head2;
            head2 = head2.next;
        }

        //循环开始前先判空,不为空则开始循环,依次比较,
        /**
         *   如果head1的节点内容比head2的节点内容小，
         *   把head1的节点内容放到新链表指向的当前节点的current，并且更新下一次要比较的节点内容
         *
         *   反之
         *   如果head1的节点内容大于或者等于head2的节点内容
         *   就把新节点的游标指向head2节点的内容
         *   并且更新下一次要比较的head2的节点内容
         *
         *
         *   一直到其中有一个链表没有数据了,就把剩下的链表的内容合并到新链表上
         */
          while (head1 != null && head2 != null) {
            if (head1.data < head2.data) {
                current.next = head1;  //新链表中，current指针的下一个结点对应较小的那个数据
                current = current.next; //current指针下移
                head1 = head1.next;
            } else {
                current.next = head2;
                current = current.next;
                head2 = head2.next;
            }
        }
        //合并剩余的元素
        if (head1 != null) { //说明链表2遍历完了，是空的
            current.next = head1;
        }

        if (head2 != null) { //说明链表1遍历完了，是空的
            current.next = head2;
        }

        return head;
    }


    /**
     *链表的反转
     * 方法1
     */
    public Node reverseList(Node head) {
        //如果链表为空或者只有一个节点，无需反转，直接返回原链表的头结点
        if (head == null || head.next == null) {
            return head;
        }
        Node current = head;
        Node next = null; //定义当前结点的下一个结点
        Node reverseHead = null;  //反转后新链表的表头
        while (current != null) {
            next = current.next;  //暂时保存住当前结点的下一个结点，因为下一次要用
            current.next = reverseHead; //将current的下一个结点指向新链表的头结点
            reverseHead = current;
            current = next;   // 操作结束后，current节点后移
        }
        return reverseHead;
    }


    /**
     * 链表的倒序输出
     * 后进先出  栈
     */
    public void reversePrint(Node head) {

        if (head == null) {
            return;
        }

        Stack<Node> stack = new Stack<Node>();  //新建一个栈
        Node current = head;

        //将链表的所有结点压栈
        while (current != null) {
                stack.push(current);  //将当前结点压栈
            current = current.next;
        }

        //将栈中的结点打印输出即可
        while (stack.size() > 0) {
            System.out.println(stack.pop().data);  //出栈操作
        }
    }

    /**
     * 链表倒叙输出2
     * 使用递归的方法
     * @param head
     * 法2是基于递归实现的，看起来简洁优雅，
     * 但有个问题：当链表很长的时候，就会导致方法调用的层级很深，有可能造成栈溢出。
     * 而方法1的显式用栈，是基于循环实现的，代码的健壮性要更好一些。
     */
    public void reversePrint2(Node head) {
        if (head == null) {
            return;
        }
        reversePrint(head.next);
        System.out.println(head.data);
    }






    /**
     * //方法：判断单链表是否有环
     * @param head
     * 如果有环,那么其中一个指针一直在循环,和另一个与他不同步向下走的指针一定会相遇,相遇表明链表中有环
     * @return
     */
    public Node hasCycle(Node head) {

        if (head == null) {
            return null;
        }
        Node first = head;
        Node second = head;

        while (second != null) {
            first = first.next;   //first指针走一步
            second = second.next.next; // second指针走两步
            if (first == second) {  //一旦两个指针相遇，说明链表是有环的
                //返回相遇的节点，用于获取环的长度
                System.out.println("相遇的节点:"+first);

                return first;
            }
        }

        return null;
    }



    /**
     * //方法：获取环的长度
     * @param head 在判断链表是否存在环时,返回的相遇的节点
     *
     * @return
     */
    public int getCycleLength(Node head) {

        if (head == null) {
            return 0;
        }
        Node current = head;
        int length = 0;
        while (current!= null) {
            length ++;
            current = current.next;   //current指针走一步
            if(current == head){
                System.out.println("环的长度："+length);
                return  length;
            }

        }


        return length;
    }



    //方法：获取环的起始点。参数length表示环的长度
    public Node getCycleStart(Node head, int cycleLength) {
        if (head == null) {
            return null;
        }

        Node first = head;
        Node second = head;
        //先让second指针走length步
        for (int i = 0; i < cycleLength; i++) {
            second = second.next;
        }

        //然后让first指针和second指针同时各走一步
        while (first != null && second != null) {
            first = first.next;
            second = second.next;

            if (first == second) { //如果两个指针相遇了，说明这个结点就是环的起始点
                System.out.println("环的起点："+first);
                return first;

            }
        }

        return null;
    }



    //判断2个单链表相交的第一个节点
    /**
     * 因为链表相交后,同一个节点只能有一个next,所以指向的对象必然是同一个,一直到链表的结尾,
     * 所以只要链表的尾部相同,只需到依次往上查找相同的节点,直到上一个节点不同
     *
     *
     * 方法一:
     * 分别把两个链表的结点放入两个栈中，这样两个链表的尾结点就位于两个栈的栈顶，
     * 接下来比较下一个栈顶，直到找到最后一个相同的结点。
     *
     *
     * 方法二"：用到快慢指针，推荐（更优解）
     *，是因为我们想同时遍历到达两个链表的尾结点。其实为解决这个问题我们还有一个更简单的办法：首先遍历两个链表得到它们的长度。在第二次遍历的时候，在较长的链表上走 |len1-len2| 步，
     * 接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个交点。
     *
     */
    //方法：求两个单链表相交的第一个交点
    public Node getFirstCommonNode(Node head1, Node head2) {
        if (head1 == null || head == null) {
            return null;
        }

        int length1 = getLength(head1);
        int length2 = getLength(head2);
        int lengthDif = 0;  //两个链表长度的差值

        Node longHead;
        Node shortHead;

        //找出较长的那个链表
        if (length1 > length2) {
            longHead = head1;
            shortHead = head2;
            lengthDif = length1 - length2;
        } else {
            longHead = head2;
            shortHead = head1;
            lengthDif = length2 - length1;
        }

        //将较长的那个链表的指针向前走length个距离
        for (int i = 0; i < lengthDif; i++) {
            longHead = longHead.next;
        }

        //将两个链表的指针同时向前移动
        while (longHead != null && shortHead != null) {
            if (longHead == shortHead) { //第一个相同的结点就是相交的第一个结点
                return longHead;
            }
            longHead = longHead.next;
            shortHead = shortHead.next;
        }

        return null;
    }


    //方法：获取单链表的长度
    public int getLength(Node head) {
        if (head == null) {
            return 0;
        }
        int length = 0;
        Node current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }


    /**
     * 节点类,表示一个节点
     */
    class Node{
        //注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
        int data;//数据域
        Node next;//指针域
        public Node(int data){
            this.data = data;
        }
    }

/*    public static void main(String[] args) {
        TestLinkList linkList = new TestLinkList();
        for (int i = 1; i <= 10; i++) {
            linkList.add(i);
        }
        TestLinkList linkList2 = new TestLinkList();
        for (int i = 0; i <= 10; i++) {
            linkList2.add(i);
        }
        linkList.add2(linkList.head);  //将头结点添加到链表当中，于是，单链表就有环了。备注：此时得到的这个环的结构，是下面的第8小节中图1的那种结构。

//        linkList.findLastNode(linkList.head,7);
//        linkList.mergeLinkList(linkList.head,linkList2.head);

//        linkList.print();
         int cycleLength =   linkList.getCycleLength(linkList.hasCycle(linkList.head));
         linkList.getCycleStart(linkList.head,cycleLength);
        System.out.println();

    }*/

}

